home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / cuj1008.zip / RAMEY.ZIP / STACK.C < prev    next >
C/C++ Source or Header  |  1991-10-14  |  6KB  |  238 lines
  1. /*
  2. Copyright (c) Robert Ramey 1991. All Rights Reserved
  3. */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <assert.h>
  7. #include <links.h>
  8. #include "psort.h"
  9. #include "stack.h"
  10.  
  11. static STACK *u_stack;        /* unused blocks */
  12. static size_t seg_size;        /* size of a memory block */
  13.  
  14. /*********************************************************************
  15. stk_windup - eliminate vestiages of stack system from memory.  Should
  16. be called only after stk_free is called for each allocated stack.
  17. Automatically called at exit.
  18. **********************************************************************/
  19. private
  20. void
  21. stk_windup()
  22. {
  23.     while(u_stack->current.count--){
  24.         felem(delink((ADDRESS)u_stack, 0), 1);
  25.     }
  26.     felem((ADDRESS)u_stack, 1);
  27. }
  28. /*********************************************************************
  29. stk_init - make a new stack system
  30. **********************************************************************/
  31. unsigned int
  32. stk_init(size, count)
  33. size_t size;
  34. unsigned int count;
  35. {
  36.     unsigned int i;
  37.     ADDRESS blk_ptr;
  38.  
  39.     seg_size = size;
  40.  
  41.     u_stack = stk_alloc();
  42.     if(u_stack == (STACK *)NULL)
  43.         return FALSE;
  44.  
  45.     for(i = 0;i < count; ++i){
  46.         blk_ptr = mkelem(seg_size, 1);
  47.         if(blk_ptr == (ADDRESS)NULL)
  48.             break;
  49.         enlink((ADDRESS)u_stack, blk_ptr, 0);
  50.     }
  51.     onexit(stk_windup);
  52.     return u_stack->current.count = i;
  53. }
  54. /*********************************************************************
  55. stk_free - free up space used by a stack
  56. **********************************************************************/
  57. void
  58. stk_free(stk)
  59. STACK *stk;
  60. {
  61.     /* move blocks onto unused list */
  62.     while(stk->current.count--){
  63.         ++u_stack->current.count;
  64.         enlink((ADDRESS)u_stack, delink((ADDRESS)stk, 0), 0);
  65.     }
  66.  
  67.     /* free root of block list */
  68.     felem((ADDRESS)stk, 1);
  69.  
  70.     return;
  71. }
  72. /*********************************************************************
  73. stk_alloc - make a new stack
  74. **********************************************************************/
  75. STACK *
  76. stk_alloc()
  77. {
  78.     STACK *stk;
  79.  
  80.     /* initialize root node to zero */
  81.     stk = (ADDRESS)mkelem(sizeof(STACK), 1);
  82.     if(stk == (STACK *)NULL){
  83.         return (STACK *)NULL;
  84.     }
  85.  
  86.     /* initialize stack control structure */
  87.     link((ADDRESS)stk, NULL, 0);
  88.     stk->frame_count = 0;
  89.     stk->current.count = 0;
  90.     stk->current.size = 0;
  91.     stk->previous = stk->current;
  92.     stk->pushed = stk->current;
  93.     return stk;
  94. }
  95. /*********************************************************************
  96. stk_avl - return size remaining in current segment
  97. **********************************************************************/
  98. /*
  99. size_t
  100. stk_avl(stk)
  101. STACK *stk;
  102. {
  103.     return stk->current.count ? stk->current.size : 0 ;
  104. }
  105. */
  106. /*********************************************************************
  107. stk_blks - return count of indicated type of segments
  108. **********************************************************************/
  109. /*
  110. unsigned int
  111. stk_blks(stk)
  112. STACK *stk;
  113. {
  114.     return stk->current.count;
  115. }
  116. */
  117. /*********************************************************************
  118. stk_unused - figure number of unused blocks available
  119. **********************************************************************/
  120. unsigned int
  121. stk_unused()
  122. {
  123.     return stk_blks(u_stack);
  124. }
  125. /*********************************************************************
  126. stk_end - next pointer to be allocated in stack
  127. **********************************************************************/
  128. char *
  129. stk_end(stk)
  130. STACK *stk;
  131. {
  132.     return (char *)nxtelem(stk, 0) + seg_size - stk->current.size;
  133. }
  134. /*********************************************************************
  135. stk_space - add space onto indicated stack
  136. **********************************************************************/
  137. void *
  138. stk_space(stk, size)
  139. STACK *stk;
  140. size_t size;
  141. {
  142.     char *cptr;
  143.  
  144.     /* save previous state */
  145.     stk->previous = stk->current;
  146.  
  147.     /* if its not going to fit within current segment */
  148.     if(size > stk_avl(stk)){
  149.  
  150.         /* if there are no segments in unused list */
  151.         if(nxtelem((ADDRESS)u_stack, 0) == (ADDRESS)NULL)
  152.             return (ADDRESS)NULL;
  153.  
  154.         /* get a segment from unused list */
  155.         enlink((ADDRESS)stk, delink((ADDRESS)u_stack, 0), 0);
  156.         /*
  157.         {
  158.             ADDRESS ptr;
  159.             ptr = delink((ADDRESS)u_stack, 0);
  160.             enlink((ADDRESS)stk, ptr, 0);
  161.         }
  162.         */
  163.         stk->current.size = seg_size;
  164.         --u_stack->current.count;
  165.         ++stk->current.count;
  166.     }
  167.     cptr = ((char *)nxtelem((ADDRESS)stk, 0) + seg_size - stk->current.size);
  168.     stk->current.size -= size;
  169.     return (void *)cptr;
  170. }
  171. /*********************************************************************
  172. stk_drop - shorten stack by last allocated amount.
  173. **********************************************************************/
  174. void
  175. stk_drop(stk)
  176. STACK *stk;
  177. {
  178.     stk->current.size = stk->previous.size;
  179.     if(stk->current.size == seg_size){
  180.         enlink((ADDRESS)u_stack, delink((ADDRESS)stk, 0), 0);
  181.         ++(u_stack->current.count);
  182.         --stk->current.count;
  183.         stk->previous.size =
  184.         stk->current.size = 0;
  185.     }
  186.     return;
  187. }
  188. /*********************************************************************
  189. stk_push - create a stack frame by pushing previous frame onto stack
  190. and saveing current frame.
  191. **********************************************************************/
  192. int
  193. stk_push(stk)
  194. STACK *stk;
  195. {
  196.     STK_BLK *bptr;
  197.  
  198.     bptr = (STK_BLK *)stk_space(stk, sizeof(STK_BLK));
  199.     if(bptr == (STK_BLK *)NULL)
  200.         return FALSE;
  201.     *bptr = stk->pushed;
  202.     stk->pushed = stk->current;
  203.     ++stk->frame_count;
  204.     return TRUE;
  205. }
  206. /*********************************************************************
  207. stk_pop - restore stack to frame previous to last stk_push
  208. **********************************************************************/
  209. int
  210. stk_pop(stk)
  211. STACK *stk;
  212. {
  213.     /* check for stack under flow */
  214.     if(stk->frame_count == 0)
  215.         return FALSE;
  216.  
  217.     --stk->frame_count;
  218.  
  219.     /* move blocks onto unused list */
  220.     while(stk->pushed.count != stk->current.count){
  221.         --stk->current.count;
  222.         ++u_stack->current.count;
  223.         enlink((ADDRESS)u_stack, delink((ADDRESS)stk, 0), 0);
  224.     }
  225.  
  226.     /* adjust size of current block */
  227.     stk->current.size = stk->pushed.size;
  228.  
  229.     /* restore previous frame */
  230.     stk->pushed = *((STK_BLK *)stk_end(stk) - 1);
  231.  
  232.     /* remove frame from stack */
  233.     stk->previous = stk->current;
  234.     stk->previous.size += sizeof(STK_BLK);
  235.     stk_drop(stk);
  236.     return TRUE;
  237. }
  238.